package com.zxy.leetcode._00000_00099._00090_00099;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/restore-ip-addresses/
 *
 * 复原IP地址
 * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 * 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 *
 * 标签：回溯算法
 */
public class Test00093 {

    public static void main(String[] args) {
        Test00093 test = new Test00093();
        System.out.println(test.restoreIpAddresses("0000"));
        System.out.println(test.restoreIpAddresses("25525511135"));
        System.out.println(test.restoreIpAddresses("010010"));
        System.out.println(test.restoreIpAddresses("101023"));
    }

    public List<String> restoreIpAddresses(String s) {
        if (s.length() < 4 || s.length() > 12) {
            return Collections.emptyList();
        }

        List<String> result = new ArrayList<>();
        LinkedList<String> selectStr = new LinkedList<>();
        backtrack(result, selectStr, 0, 0, s);
        return result;
    }

    private void backtrack(List<String> result, LinkedList<String> selectStr, int segId, int index, String allStr) {
        // IP是4小段
        if (segId == 4 && selectStr.size() == 4 && index == allStr.length()) {
            result.add(String.join(".", selectStr));
            return;
        }

        if (segId >= 4 || index > allStr.length()) {
            return;
        }

        // 3代表IP段中一小段的最大长度
        for (int i=1; i<=3; i++) {
            if (index + i > allStr.length()) {
                break;
            }
            // 剩下的几段IP是否足够
            if (index + i + (3-segId) > allStr.length()) {
                break;
            }

            String str = allStr.substring(index, index + i);
            if (!check(str)) {
                break;
            }
            selectStr.add(str);
            backtrack(result, selectStr, segId + 1, index + i, allStr);
            selectStr.removeLast();
        }

    }

    private boolean check(String str) {
        if (str.length() > 1 && str.charAt(0) == '0') {
            return false;
        }
        if (str.length() < 3) {
            return true;
        }
        if (str.length() > 3) {
            return false;
        }
        if (str.charAt(0) > '2') {
            return false;
        }
        int num = Integer.parseInt(str);
        return num <= 255;
    }
}
